package com.sicheng.algorithm.greedy;

/**
 * @author zsc
 * @version 1.0
 * @date 2021/11/15 21:54
 */
public class 最优分解问题 {

    /**
     * 问题描述：
     * 设n是一个正整数。现在要求将n分解为若干不相同的自然数的和，且使这些自然数的乘积最大。
     * 算法设计：
     * 对于给定的正整数n，计算最优分解方案
     * 数据输入：
     * 由文件input.txt提供输入数据。文件的第1行是正整数n。
     * 结果输出：
     * 将计算的最大乘积输出到文件output.txt。
     * <p>
     * 输入文件示例 输出文件示例
     * Input.txt output.txt
     * 10 30
     */
    public static void main(String[] args) {
        System.out.println(optimalDecomposition(10));
    }

    /**
     * 根据学过的数学知识，我们知道要分解后的乘积最大，应该是（1/2)的平方，
     * 即以前学过的正方形的面积肯定比同等周长的长方体大，所以应该将要分解的数分解为越接近的数字越好，分解的越多越好，
     * 而如果分解一个1的话对结果无影响，所以从2开始分解，每次加1，直到分解到剩下的数小于等于分解的最后一个数字为止。
     * 例如分解10=2+3+4，剩下1<4,然后为了使前面的不重复，因此把1加到4上。
     * 分解11=2+3+4，剩下2，加到4，3上，依次类推。
     */
    public static long optimalDecomposition(int n) {
        //如果要分解的数小于等于3，那么最终乘积为n-1
        if (n <= 3) {
            return n - 1;
        }

        //如果大于3
        //从2开始分解
        int i = 0;
        int k = 2;
        int[] a = new int[10000];
        while (n > k) {
            a[i++] = k;
            n -= k;
            k++;
        }
        //如果最后剩下的数字等于最后一个数字
        if (n == a[i - 1]) {
            n--;
            a[i - 1]++;
        }

        //对前面的数字从后向前+1
        while (n > 0) {
            for (int j = i - 1; j >= 0; j--) {
                a[j] += 1;
                n--;
                if (n == 0)
                    break;
            }
        }

        //求乘积
        long maxProduct = 1;
        for (int j = 0; j < i; j++) {
            maxProduct *= a[j];
        }

        return maxProduct;
    }
}
